1. Field of the Invention
The present invention generally relates to computer networks and more particularly to channel equalization and collision detection in computer networks.
2. Related Art
Today, computer networks, such as local area network (“LAN”) 101, shown in FIG. 1, are utilized to connect numerous devices. For example, LAN 101 may be used to connect several devices, such as personal computer 102, printer 106, personal digital assistant (“PDA”) 104, and laptop 108. LAN 101 provides a broadcast channel, which is shared by all devices capable of communication via LAN 101.
When a communications network, such as LAN 101 has many devices connected to one another, the devices may interfere with signals intended for another device in the network and, for example, may echo such signals. For instance, when personal computer 102 sends signal 110 to an intended receiver, for example, laptop 108, signal 110 is sent over a transmission medium, for example, home telephone line. The transmission medium for LAN 101 is a broadcast channel, in which other connected devices, such as PDA 104 may receive the signal, as shown by signal 112. As with any electrical transmissions circuit, if an impedance mismatch exists between the transmission medium and PDA 104, then signal 112 may be reflected, as shown by signal 114. Accordingly, signal 116 would contain reflections when it reaches laptop 108, and such reflections or echoes may cause errors in the signal received by laptop 116, which would increase the number of transmission errors.
Another common source of signal distortion is intersymbol interference (“ISI”), which is typically caused by the transmission medium of LAN 101. Typical wired transmission media, such as the twisted pair phone wiring used in LAN 101, have frequency dependent dispersion, and thus are typically band-limited. According to known digital communications theories, a band-limited transmission medium effectively disperses transmitted symbols in time. In other words, if an impulse signal is sent through a band-limited transmission medium it will be dispersed in time when it is received. ISI occurs when the impulse response of a band-limited transmission medium is longer in duration than the duration between transmitted symbols.
To mitigate the distortive effects of ISI and echoes, an adaptive equalizer may be used. Adaptive equalizers can accommodate time-varying conditions of transmission medium. Also, an adaptive equalizer can estimate a model of the distortive effects of ISI and echoes in the transmission medium. Once an accurate model of the interference is ascertained, the adaptive equalizer may undo the distortive effects of the transmission medium.
Furthermore, a major source of transmission problems in a broadcast channel is caused by the ability of each device to transmit autonomously. In other words, multiple devices may transmit packets simultaneously and, consequently, disrupt each other's transmission. For instance, since the transmission medium for LAN 101 is a broadcast channel, when personal computer 102 sends signal 110 to laptop 108, PDA 104 may simultaneously transmit a signal to printer 106. When two or more network devices begin transmitting signals on the transmission medium at the same time, a contention will occur. Such contentions are typically referred to as packet collisions. Packet collisions reduce the overall throughput of LAN 101, since the transmissions from each network device must be resent.
Conventionally, several different methods are used to reduce packet collisions. For example, in some existing systems, if a first device detects that a second device is using the transmission medium, then the first device will wait until the second device finishes its transmission. According to 802.3 Institute of Electronics and Electrical Engineers (“IEEE”) standard, i.e. Ethernet standard, the first device waits for a delineating event, which is the end of the packet of the second device. After such delineating event, the first device further waits a pseudo-random amount of integer slots periods for up to two (2) slot periods, in which a slot period is a specific fixed amount of time for the Ethernet standard. If a packet collision occurs again on the next attempt, the range is increased from two (2) slot periods to four (4) slot periods, so that the device will wait from one (1) to four (4) time slots to transmit again. The range doubles each time, but stops increasing at 1024 time slots. In addition to the techniques employed to avoid subsequent packet collisions by delaying transmission, some implementations may require devices to detect packet collisions and to cease any concurrent transmission upon detecting a packet collision.
There are several methods for detecting packet collisions. One method is to subtract the device's own transmit signal from the aggregate receive signal, so that a device can then detect signal energy caused by interfering devices. For example, in FIG. 2, network device 200 may send transmit signal 202, which is sent through a channel modeled by channel distortion 204. Channel distortion 204 may include several types of distortion, such as ISI or echoes, which give rise to distorted signal 206. In addition to the distortion caused by channel distortion 204, transmit signal 202 may encounter additive noise 208, which may arise from electromagnetic noise sources, such as spark plug ignition or radio interference. Additive noise 208 can be typically modeled as a zero mean Gaussian noise source. If another device is transmitting at the same time, distorted transmit signal 210 is added to an interfering signal 220, which is originated from interferer 214. The transmission of interferer 214 may also encounter sources of distortion and noise, such as channel distortion 216 and additive noise 218. In general, interfering signal 220 can be modeled as a linear interference. In other words, interfering signal 220 can be added to distorted transmit signal 210, as shown conceptually by adder 212. As a result, receive signal 222 contains distorted transmit signal 210 as well as interfering signal 220. Since receive signal 222 can be distorted by interfering signal 220, receive signal 222 may not be received reliably. If a packet collision is not detected until after transmission of a packet is finished, then network throughput can be degraded because of the need for retransmission of a whole packet.
To ensure reliable communications and increase network throughput, some LAN architectures may utilize adaptive equalizer 300 of FIG. 3 to also detect packet collisions. Network device 200 typically contains adaptive equalizer 300, which is normally used for removing distortion from a receive signal from other devices. Adaptive equalizer 300 isolates interfering signal 220 by taking an equalized output and subtracting from transmit signal 202, wherein the equalized output will ideally approximate transmit signal 202. Thus, interfering signal 220 can be isolated, albeit distorted since the adaptive equalizer 300 removes channel distortion 204 and not channel distortion 216 that was experienced by interfering signal 220. Nonetheless, if an interferer 214 is present, the isolated interference signal will contain energy then a collision can be detected and network device 200 stops sending transmit signal 202. However, if the filter taps of the adaptive equalizer are not adequately adapted, then interfering signal 220 may not be reliably isolated, thus making the detection process unreliable.
In operation, as shown in FIG. 3, adaptive equalizer 300 is presented with a receive signal to filter input 306. Filter input 306 is then multiplied by filter tap 308 by way of multiplier 310. Output of unit delay 312 is multiplied by filter tap 314 by way of multiplier 316. The products from multiplier 310 and 316 are added by adder 318. After the last accumulation, filter output 320 is produced. Next, filter error 332 is determined by taking the difference between filter output 320 and a desired signal. The desired signal can be a training sequence 336, such as a preamble, or decision output 326. Either desired signal can be selected by switch 334. The difference between filter output 320 and switch output 328 is determined by way of adder 330. Error signal 332 is then used to update filter taps 380. Also, after filter output 320 is computed, filter input 306 is stored in delay-line 384.
The desired signal in this case is a training sequence that appears at the beginning of the packet. For example, the transmitter and receiver may share a common known sequence. In such a scheme, the transmitter transmits the common sequence to the receiver. The receiver knows exactly how the unperturbed sequence should appear before being disturbed by the channel. This gives adaptive equalizer 300 a reference to estimate the distortion. Using a known sequence to undo the distortive effects of transmission medium of LAN 101 is a common bootstrapping method used in digital communications, commonly known as a preamble.
However, an adaptive equalizer, such as adaptive equalizer 300, which is generally present in network device 200 to equalize the channel, have many drawbacks for detecting packet collisions. Although adaptive equalizer 300 can be used to digitally subtract the transmit signal from the receive signal, adaptive equalizer 300 requires a training sequence to estimate channel distortion 204 and such training may require a very long duration, which duration could be longer than the required time for a device to react to a packet collision, as dictated by system requirements. Accordingly, adaptive equalizer 300 substantially suffers from lack of swiftness in reacting to detection of packet collisions.
Accordingly, there is an intense need in the art for designs and methods of detecting packet collisions, which provide swift and reliable packet collision detection as well as cost-effective, less complex and memory-efficient implementations.